package lcof2

import "math"

// https://leetcode.cn/problems/M1oyTv/
func minWindow(s string, t string) string {
	need, window := make(map[byte]int), make(map[byte]int)
	for i := range t {
		need[t[i]] += 1
	}
	length, start := math.MaxInt, 0
	for valid, left, right := 0, 0, 0; right < len(s); right++ {
		c := s[right]
		window[c] += 1
		if window[c] == need[c] {
			valid++
		}
		// shrink
		for valid == len(need) {
			if right-left+1 < length {
				length = right - left + 1
				start = left
			}
			d := s[left]
			if window[d] == need[d] {
				valid--
			}
			left, window[d] = left+1, window[d]-1
		}
	}
	if length == math.MaxInt {
		return ""
	}
	return s[start : start+length]
}
